/**
 * https://leetcode.cn/problems/maximum-number-of-operations-with-the-same-score-ii/submissions/582017306/
 * 3040.相同分数的最大操作数目 II 1709
 * medium 陈贝纯 11.21
 * 区间dp
 */

class Solution {
public:
    int memo[2100][2100];
    int dfs(vector<int>& nums,int i,int j,int target){
        if(i>=j)
        return 0;
        if(memo[i][j]!=-1)
            return memo[i][j];
        int ans=0;
        if(nums[i]+nums[i+1]==target)
        ans=max(ans,1+dfs(nums,i+2,j,target));
        if (nums[j - 1] + nums[j] == target) 
           ans = max(ans, 1 + dfs(nums,i, j - 2,target));
        if (nums[i] + nums[j] == target)
            ans = max(ans, 1 + dfs(nums,i + 1, j - 1,target));
        memo[i][j] = ans;
        return ans;
    }
    int maxOperations(vector<int>& nums) {
        int n=nums.size();
        memset(memo,-1,sizeof(memo));
        int res=0;
        res=max(res,dfs(nums,0,n-1,nums[0]+nums[n-1]));
        memset(memo,-1,sizeof(memo));
        res=max(res,dfs(nums,0,n-1,nums[0]+nums[1]));
        memset(memo,-1,sizeof(memo));
        res=max(res,dfs(nums,0,n-1,nums[n-2]+nums[n-1]));
        return res;
    }
};